package com.cjm.algorithm.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @see <a href=https://leetcode-cn.com/problems/triangle>三角形最小路径和</a>
 * {@link <a href=https://leetcode-cn.com/problems/triangle>三角形最小路径和</a>}
 */
public class MinimumTotal120 {
    public static int minimumTotal(List<List<Integer>> triangle) {
        // list 0 -> 1个元素
        // list 1 -> 2个元素
        // list 2 -> 3个元素
        // list 3 -> 4

        int n = triangle.size();
        // dp[i][j] 表示从点 (i, j) 到底边的最小路径和。
        int[][] dp = new int[n + 1][n + 1];
        // 从三角形的最后一行开始递推。
        for (int i = n - 1; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle.get(i).get(j);
            }
        }
        return dp[0][0];
    }


    public static void main(String[] args) {
        /*List<Integer> a = Arrays.asList(2);
        List<Integer> b = Arrays.asList(3, 4);
        List<Integer> c = Arrays.asList(6, 5, 7);
        List<Integer> d = Arrays.asList(4, 1, 8, 3);

        List<List<Integer>> lists = Arrays.asList(a, b, c, d);*/
        /*List<Integer> a = Arrays.asList(-10);
        List<List<Integer>> lists = Arrays.asList(a);*/
        List<Integer> a = Arrays.asList(-1);
        List<Integer> b = Arrays.asList(2, 3);
        List<Integer> c = Arrays.asList(1, -1, -3);

        List<List<Integer>> lists = Arrays.asList(a, b, c);
        System.err.println(minimumTotal(lists));
    }
}
